package Leetcode.图;

import java.util.*;

/**
 * @ClassName 重新规划路线
 * @since: 2023/9/4 10:33
 * @auth: kirito
 * @description:
 **/
public class 重新规划路线 {
    public int minReorder(int n, int[][] connections) {
        // 创建邻接数组表示城市之间的连接关系
        List<Integer>[] adjacentArr = new List[n];
        for (int i = 0; i < n; i++) {
            adjacentArr[i] = new ArrayList<Integer>();
        }

        // 将连接信息添加到邻接数组中
        for (int[] connection : connections) {
            adjacentArr[connection[0]].add(connection[1]);
            adjacentArr[connection[1]].add(connection[0]);
        }

        // 用于记录城市层级的数组，初始化为-1
        int[] levels = new int[n];
        Arrays.fill(levels, -1);
        levels[0] = 0;

        // 使用队列进行广度优先搜索
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(0);
        while (!queue.isEmpty()) {
            int city = queue.poll();
            List<Integer> adjacent = adjacentArr[city];

            // 遍历相邻城市
            for (int next : adjacent) {
                if (levels[next] < 0) {
                    // 如果相邻城市的层级尚未计算，则将其层级设为当前城市层级加1，并将其加入队列中
                    levels[next] = levels[city] + 1;
                    queue.offer(next);
                }
            }
        }

        // 统计需要进行路线重定向的次数
        int reorder = 0;
        for (int[] connection : connections) {
            if (levels[connection[0]] < levels[connection[1]]) {
                reorder++;
            }
        }

        // 返回路线重定向的次数
        return reorder;
    }
}
